import time


def calcTime(func):
    '''
    函数修饰器, 用来计算求出最小生命值所需要的时间
    最终返回一个 list [temp, time_sum]
    '''

    def warpper(*args, **kwds):
        time_start = time.perf_counter()
        temp = func(*args, **kwds)
        time_end = time.perf_counter()
        time_sum = time_end - time_start
        return [temp, time_sum * 1000]

    return warpper

class MinSubsum:
    def __init__(self , list_in : list):
        self.listIn = list_in[0]
        self.SubarrayNums = list_in[1]
        self.Subarray = []

    @calcTime
    def splitArray(self) -> int:
        def check(x: int) -> bool: #检测函数，判断 最大子数组和为x时 其子数组数目是否满足条件
            total, cnt = 0, 1
            #子数组都是连续的，贪心，从左到右遍历数组数组
            for num in self.listIn:
                if total + num > x:
                    cnt += 1
                    total = num
                else:
                    total += num
            return cnt <= self.SubarrayNums

        #两分法 ， Left 为数组最大值(最小子数组和，此时，子数组数目为 len(self.listIn)) ，right 为数组和(最大子数组和，此时子数组数目为 1 )
        left = max(self.listIn)
        right = sum(self.listIn)
        #迭代
        while left < right:
            mid = (left + right) // 2
            if check(mid):  #逐步逼近 left 与 right
                right = mid
            else:
                left = mid + 1
        return left




if __name__ == "__main__":
    listIn = [[1,2,3,4,5] , 2]
    test0 = MinSubsum(listIn)
    print(test0.splitArray())

